package awk.datastruct.list;


import awk.datastruct.Node;

/**
 * Title: 链表的Java实现(有头单链表、无头单链表，头节点一般用来存储链表大小等)
 * 链表跟数组的区别：
 * 数组随机访问性强（通过下标进行快速定位），查找速度快；链表不能随机查找，必须从第一个开始遍历，查找效率低
 * 数组插入和删除效率低（插入和删除需要移动数据），链表插入删除速度快（因为有next指针指向其下一个节点，通过改变指针的指向可以方便的增加删除元素）
 * 数组浪费内存（每次创建数组之前必须规定数组的大小，静态分配内存，大小固定），链表内存利用率高，不会浪费内存（可以使用内存中的不连续空间，并且可以动态括展空间）
 * 数组利用下标定位，时间复杂度为O(1)，链表定位元素时间复杂度O(n)；
 * 数组插入或删除元素的时间复杂度O(n)，链表的时间复杂度O(1)。
 *
 * 循环单链表：
 * 只要将单链表的最后一个指针域（空指针）指向链表中第一个结点即可（这里之所以说第一个结点而不说是头结点是因为，如果循环单链表是带头结点的则最后一个结点的指针域要指向头结点；
 * 如果循环单链表不带头结点，则最后一个指针域要指向开始结点）。
 *
 * 参考：https://blog.csdn.net/kai8wei/article/details/45286441
 * https://blog.csdn.net/qq_38646470/article/details/79616465
 * Description: 链表结构包含两个要素： 头结点head + 链表大小size，操作包括：
 * 链表的增删
 * 链表是否为空
 * 链表的大小
 * 链表的打印输出
 * 删除链表重复节点
 * 链表倒数第K个元素
 * 链表的反转
 * 链表的倒序输出
 * 链表的中间节点
 * 链表是否有环
 * 链表节点的删除(不知道头结点的情况下)
 * 链表是否相交
 * 链表的交点
 * <p>
 * created with IDEA
 *
 * @author haifeng.wang
 * @since 2019-06-17-10:33
 */
public class LinkedList<E> {

    /**
     * 链表表头
     */
    private Node<E> head;
    /**
     * 链表大小
     */
    private int size;

    public LinkedList() {
        head = new Node<E>(null);
    }

    public Node<E> getHead() {
        return head;
    }

    /**
     * 向链表中指定位置的元素(0 - size), 返回新节点
     */
    public Node<E> add(E data, int index) throws Exception {
        if (index > size) {
            throw new Exception("超出范围...");
        }

        Node<E> cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }
        Node<E> node = new Node<E>(data);
        cur.next = node;
        size++;
        return node;
    }

    /**
     * 向链表末尾添加元素, 返回新节点
     */
    public Node<E> add(E data) throws Exception {
        return add(data, size);
    }

    /**
     * 向链表尾部添加新节点
     */
    public void add(Node<E> node) {
        Node<E> cur = head;
        while (cur.next != null) {
            cur = cur.next;
        }
        cur.next = node;

        while (node != null) {
            size++;
            node = node.next;
        }
    }

    /**
     * 删除链表中指定位置的元素(0 ~ size - 1)
     */
    public E remove(int index) throws Exception {
        if (index > size - 1 || index < 0) {
            throw new Exception("超出范围...");
        }

        Node<E> cur = head;
        for (int i = 0; i < index; i++) {
            cur = cur.next;
        }

        Node<E> temp = cur.next;
        cur.next = temp.next;
        temp.next = null;

        size--;
        return temp.data;
    }

    /**
     * 向链表末尾删除元素
     */
    public E remove() throws Exception {
        return remove(size - 1);
    }

    /**
     * @description 删除链表中的重复元素(外循环 + 内循环)
     * @author rico 时间复杂度：O(n^2)
     */
    public void removeDuplicateNodes() {
        Node<E> cur = head.next;
        while (cur != null) {
            // 外循环
            Node<E> temp = cur;
            while (temp != null && temp.next != null) {
                // 内循环
                if (cur.data.equals(temp.next.data)) {
                    Node<E> duplicateNode = temp.next;
                    temp.next = duplicateNode.next;
                    duplicateNode.next = null;
                    size--;
                }
                temp = temp.next;
            }
            cur = cur.next;
        }
    }

    /**
     * 找出单链表中倒数第K个元素(双指针法, 相差K - 1步)
     *
     * @param k int
     * @return 时间复杂度：O(n)
     */
    public Node<E> getEndK(int k) {
        Node<E> pre = head.next;
        Node<E> post = head.next;
        for (int i = 1; i < k; i++) {
            // pre先走k-1步
            if (pre != null) {
                pre = pre.next;
            }
        }
        if (pre != null) {
            // 当pre走到链表末端时，post正好指向倒数第K个节点
            while (pre != null && pre.next != null) {
                pre = pre.next;
                post = post.next;
            }
            return post;
        }
        return null;
    }

    /**
     * 反转链表
     */
    public void reverseLinkedList() {
        // 原链表
        Node<E> cur = head.next;
        // 反转后的链表
        Node<E> pre = null;

        // 对原链表中的每个节点进行反转
        while (cur != null) {
            // 记录当前节点的下一个节点
            Node<E> tmp = cur.next;
            // 当前节点指向反转后的链表
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        // 将原链表的头结点指向反转后的链表
        head.next = pre;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public void print() {
        Node<E> cur = head.next;
        while (cur != null) {
            System.out.print(cur.data + " ");
            cur = cur.next;
        }
        System.out.println();
    }

    public void reversePrint(Node<E> head) {
        if (head.next != null) {
            reversePrint(head.next);
            System.out.print(head.next.data + " ");
        }
    }

    /**
     * 寻找单链表中的中间节点(双指针法)
     */
    public void printMiddleNodes() {
        // 慢指针
        Node<E> index1 = head.next;
        // 快指针
        Node<E> index2 = head.next;
        if (head.next == null) {
            System.out.println(index1.data);
        }
        while (index2 != null && index2.next != null && index2.next.next != null) {
            index1 = index1.next;
            index2 = index2.next.next;
        }
        System.out.print(index1.data);
        if (index2.next != null) {
            // 当链表长度为偶数时，打印第二个中间节点
            System.out.println(index1.next.data);
        }
    }

    /**
     * 判断单链表是否有环(双指针法)
     */
    public boolean hasLoop() {
        // 慢指针
        Node<E> index1 = head.next;
        // 快指针
        Node<E> index2 = head.next;
        while (index2 != null && index2.next != null && index2.next.next != null) {
            index1 = index1.next;
            index2 = index2.next.next;
            if (index1 == index2) {
                return true;
            }
        }
        return false;
    }

    /**
     * 在不知道头结点的前提下，删除指定节点
     */
    public boolean deleteNodeWithoutHead(Node<E> node) {
        if (node == null || node.next == null) {
            // 当指定节点为空或者为尾节点时，无法删除
            return false;
        }

        Node<E> next = node.next;

        // 将后继节点的内容复制到当前节点
        node.data = next.data;
        node.next = next.next;

        // 将后继节点清空
        next.next = null;
        next.data = null;
        return true;
    }

    /**
     * 判断当前链表与目标链表是否相交(相交与否取决于尾节点是否相同)
     */
    public boolean isIntersect(LinkedList<E> list2) {
        // 当前链表
        Node<E> cur1 = head.next;
        // 目标链表
        Node<E> cur2 = list2.getHead().next;

        // 两链表有一个为空，则返回 false
        if (cur1 == null || cur2 == null) {
            return false;
        }

        // 遍历到第一个链表的尾节点
        while (cur1.next != null) {
            cur1 = cur1.next;
        }

        // 遍历到第二个链表的尾节点
        while (cur2.next != null) {
            cur2 = cur2.next;
        }
        // 相交与否取决于尾节点是否相同
        return cur1 == cur2;
    }

    /**
     * 返回两链表的交点(若不相交 ， 返回null)
     */
    public Node<E> getIntersectionPoint(LinkedList<E> list2) {
        // 当前链表
        Node<E> cur1 = head.next;
        // 目标链表
        Node<E> cur2 = list2.getHead().next;

        // 先判断是否相交
        if (this.isIntersect(list2)) {
            // 让长度较长的链表先移动step步
            int step = Math.abs(list2.size - this.size);
            if (list2.size > this.size) {
                while (step > 0) {
                    cur2 = cur2.next;
                    step--;
                }
            } else if (list2.size < this.size) {
                while (step > 0) {
                    cur1 = cur1.next;
                    step--;
                }
            }

            //两个指针同时移动，一旦指向同一个节点，即为交点
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }
        return null;
    }

    public int size() {
        return size;
    }
}